package syf.tree;



public class BinaryTree {
    public static void main(String[] args) {

        HeroNode root=new HeroNode(1,"lisi");
        HeroNode node2=new HeroNode(2,"wangwu");
        HeroNode node3=new HeroNode(3,"songyf");
        HeroNode node4=new HeroNode(4,"zhangsan");
        HeroNode node5=new HeroNode(5,"cqust");
        BinaryTre binaryTre=new BinaryTre(root);
        root.setLeft(node2);
        root.setRight(node3);
        node3.setRight(node4);
        node3.setLeft(node5);
        System.out.println("==================遍历=====================");
        binaryTre.preOrder();
        System.out.println("==============");
        binaryTre.midOrder();
        System.out.println("==============");
        binaryTre.lastOrder();
        System.out.println("===================查找和查找次数====================");
        HeroNode res=binaryTre.lastSearch(5);
        System.out.println(res);
//        System.out.println("=====================删除===========================");
//        binaryTre.lastDelete(3);
//        System.out.println("=====================删除后查找===========================");
//        binaryTre.midOrder();
        System.out.println("=====================改变删除规则后删除===========================");
        binaryTre.delete(5);
        System.out.println("=====================改变删除规则后查找===========================");
        binaryTre.preOrder();


    }
}

/**
 * 数
 */
class BinaryTre{
    private HeroNode root;
    public BinaryTre(HeroNode root) {
        this.root = root;
    }
    //前序遍历
     public void preOrder(){
        if (root!=null){
            root.preOrder();
        }else {
            System.out.println("空树");
        }
     }
    //中序遍历
    public void midOrder(){
        if (root!=null){
            root.midOrder();
        }else {
            System.out.println("空树");
        }
    }
    //后续遍历
    public void lastOrder(){
        if (root!=null){
            root.lastOrder();
        }else {
            System.out.println("空树");
        }
    }
    //前序查找
    public HeroNode preSearch(int no){
        if (root!=null){
            return root.preSearch(no);
        }else {
            System.out.println("空树");
            return null;
        }
    }
    //中序查找
    public HeroNode midSearch(int no){
        if (root!=null){
            return root.midSearch(no);
        }else {
            System.out.println("空树");
            return null;
        }
    }
    //后续查找
    public HeroNode lastSearch(int no){
        if (root!=null){
            return root.lastSearch(no);
        }else {
            System.out.println("空树");
            return null;
        }
    }
    //前序删除
    public void preDelete(int no){
        if (root==null){
            System.out.println("空树");
        }else {
            HeroNode hero=root.preDelete(no);
            if (hero==root){
                root=null;
            }
        }
    }
    //中序删除
    public void midDelete(int no){
        if (root==null){
            System.out.println("空树");
        }else {
            HeroNode hero=root.midDelete(no);
            if (hero==root){
                root=null;
            }
        }
    }
    //后序删除
    public void lastDelete(int no){
        if (root==null){
            System.out.println("空树");
        }else {
            HeroNode hero=root.lastDelete(no);
            if (hero==root){
                root=null;
            }
        }
    }

    /**
     * 被删除的非叶子节点且它只有一个节点，则该节点代替
     *
     * @param no 编号
     */
    public void delete(int no){
        if (root==null){
            System.out.println("空树");
        }else {
            //被删除的非叶子节点且它只有一个节点，则该节点代替,不止一个的话，将左节点代替该节点
            if (root.getNo()==no){
                if (root.getLeft()!=null&&root.getRight()!=null){
                    root.getLeft().setRight(root.getRight());
                    root=root.getLeft();
                }else if (root.getLeft()==null){
                    root=root.getRight();
                }else {
                    root=root.getLeft();
                }
            }else {
                root.delete(no);
            }
        }
    }
}

/**
 * 英雄节点
 */
class HeroNode{
    private Integer no;
    private String name;
    private HeroNode left;//默认为空
    private HeroNode right;//默认为空

    public HeroNode(Integer no, String name) {
        this.no = no;
        this.name = name;
    }

    public Integer getNo() {
        return no;
    }

    public void setNo(Integer no) {
        this.no = no;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public HeroNode getLeft() {
        return left;
    }

    public void setLeft(HeroNode left) {
        this.left = left;
    }

    public HeroNode getRight() {
        return right;
    }

    public void setRight(HeroNode right) {
        this.right = right;
    }

    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                '}';
    }

    /**
     * 前序遍历，先输出父节点，再输出左节点，最后输出右节点
     */
    public void preOrder(){
        //先输出父节点，后续遍历到什么就输出什么，先左后右
        System.out.println(this);
        //递归遍历左节点
        if (this.left!=null){
            this.left.preOrder();
        }//递归遍历右节点
        if (this.right!=null){
            this.right.preOrder();
        }
    }
    //中序遍历
    public void midOrder(){
        //先递归遍历到最左边
        if (this.left!=null){
            this.left.midOrder();
        }//输出当前节点
        System.out.println(this);
        //再遍历当前节点的右边
        if (this.right!=null){
            this.right.midOrder();
        }
    }
    //后序遍历
    public void lastOrder(){
        //先遍历到最左边
        if (this.left!=null){
            this.left.lastOrder();
        }//再遍历到最右边
        if (this.right!=null){
            this.right.lastOrder();
        }
        System.out.println(this);
    }
    //前序查找,找到就结束
    public HeroNode preSearch(int no){
        if (this.no==no){
            System.out.println("前序查找");
            return this;
        }
        else {
            HeroNode res=null;
            if (this.left != null) {
                res=this.left.preSearch(no);
            }
            System.out.println("前序查找");
            if (res!=null){
                return res;
            }
            if (this.right != null) {
                res=this.right.preSearch(no);
            }
            return res;
        }
    }
    //中序查找
    public HeroNode midSearch(int no){
        HeroNode res=null;
        //先从左边找
        if (this.left!=null) {
            res=this.left.midSearch(no);
        }//判断左边找到没有
        if (this.no==no){
            return this;
        }
        System.out.println("中序查找");
        if (res!=null){
            return res;
        }
        if (this.right!=null){
            res=this.right.midSearch(no);
        }
        return res;
    }
    //后序查找
    public HeroNode lastSearch(int no){
        HeroNode res=null;
        //先从左边找
        if (this.left!=null) {
            res=this.left.lastSearch(no);
        }
        if (res!=null){
            return res;
        }
        if (this.right!=null){
            res=this.right.lastSearch(no);
        }
        if (res!=null){
            return res;
        }
        System.out.println("后序查找");
        if (this.no==no){
            return this;
        }
        return res;
    }
    //前序删除
    public HeroNode preDelete(int no){
        if (this.no==no){
            return this;
        }else {
            HeroNode res=null;
            if (this.left!=null){
                if (this.left.no==no){
                    return this.left=null;
                }else
                res=this.left.preDelete(no);
            }
            if (this.right!=null){
                if (this.right.no==no){
                    return this.right=null;
                }else
                    res=this.right.preDelete(no);
            }
            return res;
        }
    }
    //中序删除
    public HeroNode midDelete(int no){
        if (this.left!=null){
            if (this.left.no==no){
                return this.left=null;
            }else
                this.left.midDelete(no);
        }
        if (this.no==no)
            return this;
        if (this.right!=null){
            if (this.right.no==no){
                return this.right=null;
            }else
                this.right.midDelete(no);
        }
        if (this.no==no)
            return this;
        else return null;
    }
    //后序删除
    public HeroNode lastDelete(int no){
        if (this.left!=null){
            if (this.left.no==no){
                return this.left=null;
            }else
                this.left.lastDelete(no);
        }
        if (this.no==no)
            return this;
        if (this.right!=null){
            if (this.right.no==no){
                return this.right=null;
            }else
                this.right.lastDelete(no);
        }
        if (this.no==no)
            return this;
        else return null;
    }

    public void delete(int no) {
        //父节点的左节点
        if (this.left!=null&&this.left.no==no){
            if (this.left.right!=null&&this.left.left!=null){
                this.left.left.right=this.left.right;
                this.left=this.left.left;
            }else if (this.getLeft()==null){
                this.left=this.left.right;
            }else {
                this.left=this.left.left;
            }
        }//父节点的右节点
        if (this.right!=null&&this.right.no==no){
            if (this.right.right!=null&&this.right.left!=null){
                this.right.left.right=this.right.right;
                this.right=this.right.left;
            }else if (this.getLeft()==null){
                this.right=this.right.right;
            }else {
                this.right=this.right.left;
            }
        }
        //递归
        if (this.left!=null){
            this.left.delete(no);
        }
        if (this.right!=null){
            this.right.delete(no);
        }
    }
}
